package com.wj.graph;

/**
 * 有向环的检测类
 * @author wen.jie
 * @date 2021/8/27 16:47
 */
public class DirectedCycle {

    //索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] marked;
    //记录图中是否有环
    private boolean hasCycle;
    //索引代表顶点，使用栈的思想，记录当前顶点有没有已经处于正在搜索的有向路径上
    private boolean[] onStack;

    public DirectedCycle(Digraph G) {
        this.marked = new boolean[G.V()];
        this.hasCycle = false;
        this.onStack = new boolean[G.V()];

        //找到图中每一个顶点，让每一个顶点作为入口，调用dfs搜索
        for (int v = 0; v < G.V(); v++) {
            if (!marked[v])
                dfs(G, v);
        }
    }

    private void dfs(Digraph G,int v) {
        marked[v] = true;
        onStack[v] = true;
        for (Integer w : G.adj(v)) {
            if(!marked[w]){
                dfs(G, w);
            }
            if (onStack[w]){
                hasCycle = true;
                return;
            }
        }
        onStack[v] = false;
    }

    public boolean hasCycle() {
        return hasCycle;
    }
}
